package com.cat.dataStructure02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/pancake-sorting/?envType=problem-list-v2&envId=array
 * @create 2025/11/1 20:04
 * @since JDK17
 */

public class Solution93 {
    void reverse(int[] arr, int l, int r) {
        while (l < r) {
            int t = arr[l];
            arr[l++] = arr[r];
            arr[r--] = t;
        }
    }

    public List<Integer> pancakeSort(int[] arr) {
        int n = arr.length;
        int[] sorted = Arrays.copyOf(arr, n);
        Arrays.sort(sorted);
        List<Integer> ans = new ArrayList<>();
        for (int i = n - 1; i >= 0; i++) {
            if (arr[i] == sorted[i]) {  // 已经处于正确的位置了
                continue;
            }
            int x = sorted[i], y = 0;
            // 找到正确的位置
            for (y = 0; y < i && arr[y] != x; y++);
            reverse(arr, 0, y);
            ans.add(y);
            reverse(arr, 0, i);
            ans.add(i);
        }

        return ans;
    }
}
